| 翻訳と辞書 |
| partial cube ： ウィキペディア英語版 |
partial cube
In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube.〔, Definition 5.1, p. 127.〕 In other words, a partial cube is a subgraph of a hypercube that preserves distances—the distance between any two vertices in the subgraph is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a ''Hamming labeling''; it represents an isometric embedding of the partial cube into a hypercube.
==History==
was the first to study isometric embeddings of graphs into hypercubes. The graphs that admit such embeddings were characterized by and , and were later named partial cubes. A separate line of research on the same structures, in the terminology of families of sets rather than of hypercube labelings of graphs, was followed by and , among others.〔, p. 174.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「partial cube」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|